"""
题目：给定一个单链表，删除链表的倒数第 N 个节点，并返回链表的头节点。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def remove_nth_from_end(head, n):
    # 创建哑节点，简化头节点被删除的情况
    dummy = ListNode(0)
    dummy.next = head

    # 初始化快慢指针，都指向哑节点
    first = dummy
    second = dummy

    # 先让first指针前进n+1步
    for _ in range(n + 1):
        first = first.next

    # 同时移动两个指针，直到first到达末尾
    while first:
        first = first.next
        second = second.next

    # 此时second指向要删除节点的前一个节点
    second.next = second.next.next  # 删除节点

    return dummy.next  # 返回新的头节点


# 辅助函数
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
head = create_linked_list([1, 2, 3, 4, 5])
new_head = remove_nth_from_end(head, 2)
print(traverse_linked_list(new_head))  # 输出: [1, 2, 3, 5]（删除了倒数第2个节点4）
